// https://leetcode.cn/problems/construct-quad-tree/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 使用递归分治方法构建四叉树
// 2. 检查当前区域是否值相同，相同则创建叶子节点
// 3. 否则递归构建四个象限子树并创建分支节点
// 4. 时间复杂度：O(N²logN)，空间复杂度：O(logN)

// 本题辅助函数和主函数由AI生成

#include <iostream>
using namespace std;

#include <vector>

class Node 
{
public:
    bool val;
    bool isLeaf;
    Node* topLeft;
    Node* topRight;
    Node* bottomLeft;
    Node* bottomRight;
    
    Node() 
    {
        val = false;
        isLeaf = false;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf) 
    {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = NULL;
        topRight = NULL;
        bottomLeft = NULL;
        bottomRight = NULL;
    }
    
    Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) 
    {
        val = _val;
        isLeaf = _isLeaf;
        topLeft = _topLeft;
        topRight = _topRight;
        bottomLeft = _bottomLeft;
        bottomRight = _bottomRight;
    }
};


class Solution 
{
public:
    Node* construct(vector<vector<int>>& grid) 
    {
        return buildTree(grid, 0, 0, grid.size());
    }
private:
    Node* buildTree(vector<vector<int>>& grid, int x, int y, int len)
    {
        if (isSame(grid, x, y, len))
        {
            return new Node(grid[x][y] == 1, true);
        }

        int half = len / 2;
        Node* tLeft = buildTree(grid, x, y, half);
        Node* tRight = buildTree(grid, x, y + half, half);
        Node* bLeft = buildTree(grid, x + half, y, half);
        Node* bRight = buildTree(grid, x + half, y + half, half);

        return new Node(false, false, tLeft, tRight, bLeft, bRight);
    }

    bool isSame(vector<vector<int>>& grid, int x, int y, int len)
    {
        bool val = grid[x][y];
        for (int i = x ; i < x + len ; i++)
        {
            for (int j = y ; j < y + len ; j++)
            {
                if (grid[i][j] != val)
                {
                    return false;
                }
            }
        }
        return true;
    }
};

// 打印四叉树的辅助函数
void printQuadTree(Node* node, string prefix = "") 
{
    if (node == nullptr) return;
    
    cout << prefix;
    if (node->isLeaf) 
    {
        cout << "Leaf: " << (node->val ? "1" : "0") << endl;
    } 
    else 
    {
        cout << "Node" << endl;
        printQuadTree(node->topLeft, prefix + "  ");
        printQuadTree(node->topRight, prefix + "  ");
        printQuadTree(node->bottomLeft, prefix + "  ");
        printQuadTree(node->bottomRight, prefix + "  ");
    }
}

// 释放四叉树内存
void deleteQuadTree(Node* node) 
{
    if (node == nullptr) return;
    if (!node->isLeaf) 
    {
        deleteQuadTree(node->topLeft);
        deleteQuadTree(node->topRight);
        deleteQuadTree(node->bottomLeft);
        deleteQuadTree(node->bottomRight);
    }
    delete node;
}

int main() 
{
    Solution solution;
    
    // 测试用例1: 4x4网格
    cout << "=== 测试用例1 ===" << endl;
    vector<vector<int>> grid1 = 
    {
        {1, 1, 0, 0},
        {1, 1, 0, 0},
        {0, 0, 1, 1},
        {0, 0, 1, 1}
    };
    Node* result1 = solution.construct(grid1);
    printQuadTree(result1);
    
    // 测试用例2: 2x2网格
    cout << "\n=== 测试用例2 ===" << endl;
    vector<vector<int>> grid2 = 
    {
        {1, 0},
        {0, 1}
    };
    Node* result2 = solution.construct(grid2);
    printQuadTree(result2);
    
    // 测试用例3: 全1的4x4网格
    cout << "\n=== 测试用例3 ===" << endl;
    vector<vector<int>> grid3 = 
    {
        {1, 1, 1, 1},
        {1, 1, 1, 1},
        {1, 1, 1, 1},
        {1, 1, 1, 1}
    };
    Node* result3 = solution.construct(grid3);
    printQuadTree(result3);
    
    // 测试用例4: 全0的2x2网格
    cout << "\n=== 测试用例4 ===" << endl;
    vector<vector<int>> grid4 = 
    {
        {0, 0},
        {0, 0}
    };
    Node* result4 = solution.construct(grid4);
    printQuadTree(result4);
    
    // 释放内存
    deleteQuadTree(result1);
    deleteQuadTree(result2);
    deleteQuadTree(result3);
    deleteQuadTree(result4);
    
    cout << "\n=== 所有测试完成 ===" << endl;
    
    return 0;
}